1564. Put Boxes Into the Warehouse I
Medium

You are given two arrays of positive integers, boxes and warehouse, representing the heights of some boxes of unit width and the heights of n rooms in a warehouse respectively. The warehouse's rooms are labelled from 0 to n - 1 from left to right where warehouse[i] (0-indexed) is the height of the ith room.

Boxes are put into the warehouse by the following rules:

  • Boxes cannot be stacked.
  • You can rearrange the insertion order of the boxes.
  • Boxes can only be pushed into the warehouse from left to right only.
  • If the height of some room in the warehouse is less than the height of a box, then that box and all other boxes behind it will be stopped before that room.

Return the maximum number of boxes you can put into the warehouse.

 

Example 1:

Input: boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
Output: 3
Explanation: 

We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0.
There is no way we can fit all 4 boxes in the warehouse.

Example 2:

Input: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
Output: 3
Explanation: 

Notice that it's not possible to put the box of height 4 into the warehouse since it cannot pass the first room of height 3.
Also, for the last two rooms, 2 and 3, only boxes of height 1 can fit.
We can fit 3 boxes maximum as shown above. The yellow box can also be put in room 2 instead.
Swapping the orange and green boxes is also valid, or swapping one of them with the red box.

Example 3:

Input: boxes = [1,2,3], warehouse = [1,2,3,4]
Output: 1
Explanation: Since the first room in the warehouse is of height 1, we can only put boxes of height 1.

Example 4:

Input: boxes = [4,5,6], warehouse = [3,3,3,3,3]
Output: 0

 

Constraints:

  • n == warehouse.length
  • 1 <= boxes.length, warehouse.length <= 10^5
  • 1 <= boxes[i], warehouse[i] <= 10^9
Accepted
8.5K
Submissions
13.3K
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions
Show Hint 1
Sort the boxes in ascending order, try to process the box with the smallest height first.

Average Rating: 4.75 (16 votes)

Premium

Overview

Let's think through an analogy first, that might be more relatable. Imagine that you are standing in front of a cave. The cave goes down into the earth, becoming narrower and then wider in various places. Additionally, you have several stones in hand - of varying diameters. Your goal is to throw as many of the stones inside the cave as possible. Let's think about the strategy you would use.

Firstly, if there is a bottleneck (a very narrow section) in the cave, then even if the cave becomes wider afterwards, the stone will get stuck right before the bottleneck. So for each position in the cave, the largest stone that we can insert is limited by the narrowest part of the cave before it. In other words, that position's usable diameter is limited by the minimum diameter before it.

Secondly, throwing a small stone earlier is always better than throwing it later, because if a small stone gets stuck, a larger stone will certainly get stuck, but the reverse is not true.

Therefore, our strategy would be to throw in the smallest stone first.

Now we can think of the stones as boxes, and the warehouse as the cave, where the height of each warehouse room corresponds to the diameter of the cave. The problem, and its solution, are now equivalent to the above analogy.



Approach 1: Add Smallest Boxes to the Rightmost Warehouse Rooms

Intuition

We will take a greedy approach to solve the problem. The intuition is that if each step follows the optimal strategy, then the overall arrangement of boxes will be optimal.

Imagine we have a box of height h, and we want to push it into the warehouse. We start pushing from the left, and we want to push it as far right as we can. The limiting factor on how far we can push it will be the first position in the warehouse we encounter that has a height less than h. We won't be able to push the box into this position, or into any position after it.

To make the algorithm more efficient, we will first preprocess the heights of the warehouse. Keeping in mind that the limiting factor for each position is the minimum height that comes before it, we update the height for each position so that it is no higher than this minimum. This essentially changes the warehouse array to a weakly decreasing array.

We then sort the boxes from shortest to tallest. Then, we take the shortest box remaining and push it as far right as possible through the warehouse (we have to stop when the next position is shorter than this box).

Below are the slides showing the greedy process.

Current
1 / 6

Algorithm

Because lower heights for rooms on the left will block the entry of boxes into rooms on the right, we need to preprocess the array of warehouse heights such that it becomes a non-increasing sequence. Then, we start from the smallest box and the rightmost position of the warehouse. If the current box can fit in the warehouse room, we increment the count by 1 and move on to the next box. Otherwise, we move on to the next warehouse room and check if the box will fit there.

Let nn be the number of boxes and mm be the number of rooms in the warehouse.

  • Time complexity: O(nlog(n)+m)O(n \log(n) + m) because we need to sort the boxes (O(nlogn)O(n \log n)) and iterate over the warehouse rooms and boxes (O(n+m))O(n + m))).

  • Space complexity: O(1)O(1) because we use two pointers to iterate over the boxes and warehouse rooms. If we are not allowed to modify the warehouse array, we will need O(m)O(m) extra space.



Approach 2: Add Largest Possible Boxes from Left to Right

Intuition

What if the interviewer requires us to use O(1)O(1) space and does not allow us to modify the original warehouse array? This follow-up request excludes the possibility of preprocessing the input array as we did before.

We can take a slightly different greedy approach to tackle the problem. We iterate over the warehouse rooms from left to right and use another pointer to iterate over boxes from the largest to the smallest. For each position, we discard boxes that are too tall to fit in the current warehouse room, because they won't fit in any rooms further to the right. We put the tallest possible box that can fit in this room, and save the remaining boxes for warehouse rooms further to the right.

Algorithm

For this approach, we do not need to calculate the maximum height allowed for each warehouse room. This is because boxes are sorted in decreasing order, so a room with a low height will automatically omit all boxes that are taller than it.

We start from the largest box and the leftmost position of the warehouse. When the box can fit in the warehouse room, we increment the count by 1. Otherwise, we discard the box and try a smaller one.

Below are the slides showing this new algorithm.

Current
1 / 6

The time and space complexity will be similar to Approach 1. Let nn be the number of boxes and mm be the number of rooms in the warehouse.

  • Time complexity: O(nlog(n)+m)O(n \log(n) + m) because we need to sort the boxes and iterate over the warehouse rooms and boxes.

  • Space complexity: O(1)O(1) because we use two pointers to iterate over the boxes and warehouse rooms.

A related question is LeetCode 1580. Put Boxes Into the Warehouse II. I recommend you have a go at it once you're confident you understand this problem!

Report Article Issue

Comments: 6
virtyaluk's avatar
Read More

The problem description is so confusing and counterintuitive. The first part of the overview makes it much easier to understand the problem.

6
Show 1 reply
Reply
Share
Report
Goldspear's avatar
Read More

Space complexity is not O(1), but O(n) or O(log(n)) depending on the implementation of sort() per given language. For Python, it's TimSort with O(n).

1
Show 4 replies
Reply
Share
Report
wwwap's avatar
Read More

Thanks for sharing. ;)

0
Reply
Share
Report
sirvole's avatar
Read More

My attempt to implement the Approach 2.

    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
        sorted_boxes = sorted(boxes, reverse=True)
        wi, bi, count = 0, 0, 0        
        while wi<len(warehouse) and bi<len(boxes):
            if sorted_boxes[bi] <= warehouse[wi]:
                wi += 1
                count += 1
            bi += 1
        return count

0
Reply
Share
Report
manzaloros's avatar
Read More

I'm trying to understand why the while loop in the second approach doesn't increase the time complexity to O(n^2).

0
Show 3 replies
Reply
Share
Report
Gift369's avatar
Read More

Thanks for the article!
1st approach in JS:

var maxBoxesInWarehouse = function(boxes, warehouse) {
    if (!boxes || !warehouse) return null;
    
    for (let i = 1; i < warehouse.length; i++) {
        warehouse[i] = Math.min(warehouse[i], warehouse[i - 1]);
    }
    boxes.sort((a, b) => a - b);
    let count = 0;
    
    for (let i = warehouse.length; i >= 0; i--) {
        if (count < boxes.length && boxes[count] <= warehouse[i]) count++;
    }
    return count;
};

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium